package com.zk.algorithm.backtracking;

import com.zk.algorithm.annotation.LeetCodeExplore;
import com.zk.algorithm.annotation.Medium;

@Medium
@LeetCodeExplore
public class WordSearch {

    public boolean exist(char[][] board, String word) {
        boolean[][] visited = new boolean[board.length][board[0].length]; // store the states of visited cell

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (exist(board, word, visited, i, j, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean exist(char[][] board, String word, boolean[][] visited, int i, int j, int index) {
        if (index == word.length())
            return true;

        if (i < 0 || j < 0 || i == board.length || j == board[i].length
                || board[i][j] != word.charAt(index) || visited[i][j]) {
            return false;
        }

        // ========================
        // 访问
        // ========================
        visited[i][j] = true; // mark the current cell as visited

        // ========================
        // DFS
        // ========================
        boolean exist = exist(board, word, visited, i + 1, j, index + 1)
                || exist(board, word, visited, i - 1, j, index + 1)
                || exist(board, word, visited, i, j + 1, index + 1)
                || exist(board, word, visited, i, j - 1, index + 1); // recursive call

        // ========================
        // 回溯
        // ========================
        visited[i][j] = false; // reset the current cell for next choice
        return exist;
    }

}
